package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC69 {

    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }

        long midNum = 1;
        int left = 0, right = x;
        while (left <= right) {
            midNum = (right + left) / 2;
            if (midNum * midNum <= x && (midNum + 1) * (midNum + 1) > x) {
                return (int) midNum;
            }

            if (midNum * midNum < x) {
                left = (int) midNum + 1;
            } else {
                right = (int) midNum - 1;
            }

        }

        return (int) midNum;
    }

    public static void main(String[] args) {
        LC69 an = new LC69();

        System.out.println(an.mySqrt(2147395599));
        System.out.println(Math.sqrt(2147395599));
    }
}
